home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6110 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.3 KB
  1. Path: po.CWRU.Edu!mab22
  2. From: mab22@po.CWRU.Edu (Michael A. Balfour)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: unique id for a string
  5. Date: 22 Feb 1996 19:47:22 GMT
  6. Organization: Case Western Reserve University, Cleveland, OH (USA)
  7. Message-ID: <4gih8a$b62@madeline.INS.CWRU.Edu>
  8. References: <1996Feb16.175601.114182@kuhub.cc.ukans.edu> <3129dd39.961626@news.iquest.net> <4gfpveINNe68@keats.ugrad.cs.ubc.ca>
  9. Reply-To: mab22@po.CWRU.Edu (Michael A. Balfour)
  10. NNTP-Posting-Host: kanga.ins.cwru.edu
  11.  
  12.  
  13. In a previous article, c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku) says:
  14.  
  15. >In article <3129dd39.961626@news.iquest.net>,
  16. >Robert B. Clark <rclark@iquest.net> wrote:
  17. > >On 16 Feb 96 17:56:01 CST, anh@kuhub.cc.ukans.edu wrote:
  18. > >
  19. > >>HELLO =  H * 26^4 + E * 26 ^3 +  L * 26^2 + L * 26^1 + E * 26^0
  20. > >>
  21. > >>But the id is way too big. I need something that fits within a 32-bits int 
  22. > >>or a 64-bits long.
  23. > >
  24. > >You're thinking way too hard, perhaps.  Look up the algorithm for CRCs
  25. > >(cyclic redundancy checks/codes) in Snippets or most any other popular
  26. > >programmer's reference.
  27. >
  28. >But he wants a _unique_ ID. This is not possible, since the space of possible
  29. >words is much larger than the space of 32- or even 64-bit integers. Even for a
  30. >limited dictionary of around 200,000 words, a function that _guarantees_ a
  31. >unique hash for each indentifier into a 32-bit space is difficult to find.
  32.  
  33. Actually, it's not *that* difficult to find.  Try running gperf from GNU
  34. or reading the paper cited in my previous post in this subject.  The
  35. results in the paper claim to be able to find a perfect hash function
  36. for 262,144 18-character words in 16.087 seconds on a Sun Sparc 2.
  37. Doesn't sound that difficult to me.  :)
  38.  
  39. >One way to get a unique mapping is to simply assign increasing numbers to the
  40. >200,000+ words, and use a hashing technique to quickly look up a word given its
  41. >integer tag, and look up the tag given the word. With the proper
  42. >represenatation, both operations can be done in "constant time".
  43.  
  44. Once again, using a perfect minimal hash function will provide an easy
  45. method for accomplishing this.
  46.  
  47. Mike Balfour
  48. -- 
  49. ----------------------------------+--------------------------------
  50. Mike Balfour, Partner             | BS/MS Graduate - ECMP
  51. Overload Engineering              | Case Western Reserve University
  52. "New Ideas for a Brighter Future" | Cleveland, OH
  53.